09_MDP

Tags: #◇CSINTSY #◇Computational Thinking #◇Computer Science #◇Artificial Intelligence #◇Machine Learning #◇Intelligent Systems #◇Probability #◇Data Analysis

---

◇Overview

A Markov Decision Process (MDP) is a mathematical framework for modeling decision-making in situations where outcomes are partly random and partly ...

◇Details / Theory

9. Markov Decision Processes (MDP) Reviewer

◇Overview

A Markov Decision Process (MDP) is a mathematical framework for modeling decision-making in situations where outcomes are partly random and partly under the control of a decision maker. It is the formal basis for Reinforcement Learning.

◇Markov Property

"The future is independent of the past given the present."
The next state depends only on the current state and the action taken, not on the sequence of events that preceded it.

◇Components of an MDP

An MDP is defined by the tuple $(S, A, T, R, \gamma)$:

1. States ($S$): The set of all possible situations or configurations of the environment.
2. Actions ($A$): The set of all possible moves the agent can take.
3. Transition Function ($T$) (or Model):
   $T(s, a, s') = P(s' | s, a)$
   The probability of reaching state $s'$ if we take action $a$ in state $s$.
   This models the uncertainty/randomness of the environment.
4. Reward Function ($R$):
   $R(s, a, s')$
   The immediate reward received after transitioning from $s$ to $s'$ via action $a$.
5. Discount Factor ($\gamma$):
   A number between 0 and 1 ($0 \le \gamma \le 1$).
   Determines the importance of future rewards.
   $\gamma \approx 0$: Agent is myopic (cares only about immediate reward).
   $\gamma \approx 1$: Agent is farsighted (cares about long-term cumulative reward).

◇Key Concepts

Policy ($\pi$)

A strategy or rule that tells the agent what action to take in each state. $\pi(s) \to a$ Optimal Policy ($\pi^*$): The policy that yields the highest expected cumulative reward over time.

Value Function ($V(s)$)

The expected cumulative reward the agent will receive starting from state $s$ and following a specific policy thereafter. It tells us "how good" it is to be in a specific state.

Bellman Equation

A recursive equation that decomposes the value of a state into the immediate reward plus the discounted value of the next state.
// ...existing code...
$V(s) = \max*a \sum*{s'} T(s, a, s') [R(s, a, s') + \gamma V(s')]$
This equation is used to solve for the optimal values and policy. This equation is used to solve for the optimal values and policy.

◇Solved Example: Bellman Update

Scenario:
State A: You are here. Actions: "Go Left" or "Go Right". Discount Factor ($\gamma$): 0.9.

Transitions & Rewards:

1. Action "Go Left":
   50% chance to reach State B (Value $V(B) = 10$). Reward = 0.
   50% chance to reach State C (Value $V(C) = 2$). Reward = 0.
2. Action "Go Right":
   100% chance to reach State D (Value $V(D) = 5$). Reward = 2.

Calculate Value of Actions:
Value of "Go Left":
$0.5 \times [0 + 0.9(10)] + 0.5 \times [0 + 0.9(2)]$
$0.5 \times [9] + 0.5 \times [1.8]$
$4.5 + 0.9 = 5.4$
Value of "Go Right":
$1.0 \times [2 + 0.9(5)]$
$1.0 \times [2 + 4.5]$
$6.5$

Update Value of State A:
$V(A) = \max(5.4, 6.5) = 6.5$
Optimal Policy: Go Right.

---

◇Common Pitfalls

Forgetting the discount factor $\gamma$ — it controls how much future rewards are worth vs. immediate ones. Confusing the transition function $T(s,a,s')$ (probability of reaching $s'$) with the reward $R(s,a,s')$. Not iterating the Bellman equation until convergence — one pass is generally insufficient for correct value estimates.

◇Summary

TL;DR — An MDP is defined by states, actions, transition probabilities, rewards, and discount factor $\gamma$. The Bellman equation $V(s) = \max_a \sum_{s'} T(s,a,s')[R(s,a,s') + \gamma V(s')]$ gives the optimal value function; the optimal policy picks the action maximizing this.

◇Links

Related: Source / Reference:

---

Made by 2ru17

Please contact me through discord or my the university email for any problems regarding the reviewer. Thanks!

◇References & Navigation

• Previous Topic: ◇K Means Clustering
• Next Topic: ◇Q Learning
• Related Notes: ◇Markov Decision Processes